1. Field of the Invention
The present invention is directed to a system for determining values of half-pels from a reference frame of pixels. The invention has particular utility in connection with motion compensation performed during decoding of half-pel encoded video data.
2. Description of the Related Art
Video coding systems, such as motion picture experts group (hereinafter xe2x80x9cMPEGxe2x80x9d) coding, code video data using motion vectors. These motion vectors define movement of an object (e.g., a macroblock) in the video data from a reference, or anchor, frame to a current frame. Each motion vector consists of a horizontal, or xe2x80x9cxxe2x80x9d, component and a vertical, or xe2x80x9cyxe2x80x9d component, and is the representation of the distance that the object has moved in the time between the reference frame and the current frame.
In some coding systems, motion vectors are restricted to integer values. In these coding systems, the values of pixels in the current frame are specified in terms of values of actual pixels in the reference frame. This type of coding is known as full-pel (i.e., full-pixel) coding. In other coding systems, however, an example of which is MPEG, the motion vectors can have half-integer values. In these systems, the values of pixels in the current frame are not specified solely in terms of pixels that actually exist, but rather can be specified in terms of xe2x80x9cvirtualxe2x80x9d pixels that are interpolated from existing pixels in the reference frame. This type of coding is known as half-pel (i.e., half-pixel) coding.
Motion compensation is a process which can be used to decode video data that has been coded using a half-pel coding system such as MPEG. In the case of half-pel coded video data, the motion compensation process recreates frames of video data from virtual pixels such as those described above. More specifically, in motion compensation of half-pel coded video, a motion vector is used to retrieve data for an object from a reference frame. An object is then generated which is comprised of half-pels that have been interpolated from actual pixels in the reference frame. It is noted that this object is merely a construct that used to improve the motion compensation process, and that the object is not actually displayed. After the object has been generated, a next half-pel motion vector is used to retrieve data from the object, and then to generate and display an actual object at the proper location within the current frame.
The motion compensation process described above interpolates half-pel values by a process which is known in the art as half-pel prediction filtering. Half-pel prediction filtering comprises averaging the value of a pixel corresponding to an integer (i.e., non-half-pel) part of the motion vector with a value of that pixel""s nearest neighboring pixel in the direction of increasing motion. In a case that the horizontal component of the motion vector comprises the half-pel part of the motion vector, the averaging is performed with the pixel immediately to the right of the pixel of interest. In a case that the vertical component of the motion vector comprises the half-pel part of the motion vector, the averaging is performed with the pixel immediately below the pixel of interest. In a case where both components comprise a half-pel, the averaging is performed in both the horizontal and vertical directions and with the pixel diagonally adjacent to the pixel of interest.
Thus, as is clear from the foregoing, the motion compensation process requires retrieving at least one other pixel, and potentially three other pixels, to interpolate a single half-pel. In the case of a 16xc3x9716 pixel MPEG macroblock, for example, this means that an array of 17xc3x9717 pixels must be retrieved from a frame memory in order to perform motion compensation on the macroblock. Thus, an extra 33 pixels (the difference between 17xc3x9717 pixels and 16xc3x9716 pixels), or 13% more pixels, are required to perform motion compensation on the macroblock. Certain modes of MPEG-2 use two motion vectors for each macroblock. In these modes, an array of 18xc3x9717 pixels must be retrieved from a frame memory in order to perform motion compensation. Thus, in these cases, an extra 50 pixels, or about 20% more pixels, are required to perform motion compensation on the macroblock. Retrieval and processing of extra pixels in both cases increase the time that it takes to process each macroblock.
More specifically, in conventional decoding systems, all pixels in a particular macroblock are stored sequentially in a frame-store memory. If all of these pixels are processed sequentially, a timing xe2x80x9cgapxe2x80x9d, which is proportionate to the number of extra pixels (e.g., 33 or 50 pixels), will be introduced between every two successive macroblocks in a frame of video data. This timing gap is typically introduced into both luminance and chrominance pixels in the macroblocks. To compensate for the timing gap, conventional MPEG decoders often include a high speed processing clock, together with additional hardware such as data buffers or the like. However, this solution increases the complexity of the timing and control circuitry used in such decoders, and often necessitates the use of an additional clocking frequency in a digital video receiver that includes such a decoder.
Thus, there exists a need for way to perform half-pel interpolation, particularly in the area of motion compensation, which does not introduce substantial timing gaps into video data during decoding, and which does not require significant amounts of additional hardware (e.g., memory) or an overly complex timing and control strategy.
The present invention addresses the foregoing needs by storing pixel data from a pixel array in one of a plurality of different memory segments based on a location of the pixel data in the pixel array. The invention then reads pixel data from each of the plurality of memory segments and determines a value of at least one half-pel based on the read pixel data. By storing pixel data in different memory segments and reading that pixel data from the different memory segments, it is possible to process pixels non-sequentially and, as a result, reduce any time gaps between consecutive macroblocks in a frame without the use of additional timing mechanisms and overly-complex control circuitry.
Thus, according to one aspect, the present invention is a method of, and a corresponding apparatus for, interpolating half-pels from a pixel array. The invention stores pixel data for each pixel in one of a plurality of different memory areas based on a location of the pixel within the pixel array, and determines a specific address in each one of the plurality of memory areas based on a target pixel in the pixel array. Each specific address is determined in the invention based on a location of the target pixel in the pixel array. The invention also reads, from each of the plurality of memory areas, pixel data from determined specific addresses, and determines a value of at least one half-pel for the target pixel based on the read pixel data.
In preferred embodiments of the invention, the pixel data is read from each one of the memory areas substantially concurrently. By reading the pixel data from each of the memory areas substantially concurrently, the invention reduces processing time by further reducing any timing gaps between consecutive macroblocks in a frame.
In particularly preferred embodiments, the invention is capable of interpolating half-pels by averaging a target pixel with one or more of three adjacent pixels. In these embodiments, an address of each adjacent pixel in its respective memory area is determined based on a location of the target pixel in the pixel array. Specifically, in a case that the target pixel is located in an even row and an even column in the pixel array, a specific address for each of three pixels adjacent to the target pixel is the same as a specific address for the target pixel. In a case that the target pixel is located in an even row and an odd column in the pixel array, a specific address for a pixel vertically adjacent to the target pixel is the same as a specific address of the target pixel, and specific addresses for pixels horizontally and diagonally adjacent to the target pixel comprise a row address of the target pixel and a column address of the target pixel incremented by one. In a case that the target pixel is located in an odd row and an even column in the pixel array, a specific address for a pixel horizontally adjacent to the target pixel is the same as a specific address of the target pixel, and specific addresses for pixels vertically and diagonally adjacent to the target pixel comprise a column address of the target pixel and a row address of the target pixel incremented by one. Finally, in a case that the target pixel is located in an odd row and an odd column in the pixel array, a specific address for a pixel horizontally adjacent to the target pixel comprises a row address of the target pixel and a column address of the target pixel incremented by one, a specific address for a pixel vertically adjacent to the target pixel comprises a column address of the target pixel and a row address of the target pixel incremented by one, and a specific address for a pixel diagonally adjacent to the target pixel comprises a row address of the target pixel incremented by one and a column address of the target pixel incremented by one.
By virtue of the foregoing arrangement, the invention provides a way to access a correct address in each memory area without using complex circuitry or complicated timing strategies.
According to another aspect, the present invention is an apparatus for interpolating half-pels from a pixel array. The apparatus includes a plurality of different memory areas which store pixel data for each pixel in the pixel array based on a location of the pixel within the pixel array, and circuitry which determines a specific address in each of the plurality of memory areas based on an address of a target pixel in the pixel array. The apparatus also includes a plurality of multiplexers for outputting pixel data stored at each specific address in each of the plurality of memory areas, and a half-pel interpolator which determines a value of at least one half-pel for the target pixel based on the pixel data output by the plurality of multiplexers.
According to another aspect, the invention is an apparatus for decoding coded video data. The apparatus includes a plurality of frame-store memory segments, and processing and control circuitry which receives the coded video data, which outputs a specific address of a target pixel in a frame of the coded video data, and which performs, on the coded video data, variable length decoding, inverse scanning, inverse quantization, an inverse discrete cosine transformation, and motion compensation. Circuitry in the apparatus determines a specific address in each of the plurality of frame-store memory segments based on the specific address of the target pixel output by the processing and control circuitry, and a plurality of multiplexers output pixel data stored at each specific address in each of the frame-store memory segments. A half-pel interpolator determines at least one half-pel for the target pixel based on the pixel data output by the plurality of multiplexers and outputs the at least one half-pel to the processing and control circuitry. The processing and control circuitry performs the motion compensation based on the at least one half-pel determined by the half-pel interpolator.
According to another aspect, the invention is a digital television system which includes a tuner that is capable of receiving coded video data over one of a plurality of channels, a video decoder which decodes the coded video data and which outputs uncoded video data, a display processor which generates images based on the uncoded video data, and a video display for displaying the images generated by the display processor. The video decoder includes a plurality of frame-store memory segments, and processing and control circuitry which receives the coded video data, which outputs a specific address of a target pixel in a frame of the coded video data, and which performs, on the coded video data, variable length decoding, inverse scanning, inverse quantization, an inverse discrete cosine transformation, and motion compensation in order to generate the uncoded video data. The video decoder also includes circuitry which determines a specific address in each of the plurality of frame-store memory segments based on the specific address of the target pixel output by the processing and control circuitry, a plurality of multiplexers which output pixel data stored at each specific address in each of the frame-store memory segments, and a half-pel interpolator which determines at least one half-pel for the target pixel based on the pixel data output by the plurality of multiplexers, and which outputs the at least one half-pel to the processing and control circuitry. In the invention, the processing and control circuitry performs the motion compensation based on the at least one half-pel determined by the half-pel interpolator.
The foregoing aspect of the invention incorporates the advantages of the present invention, which were described above, into a digital television system. As a result, the invention provides for a digital television system (or any other MPEG-type system, for that matter) which depicts objects, and in particular object motion, more efficiently and more rapidly than its conventional counterparts.
This brief summary has been provided so that the nature of the invention may be understood quickly. A more complete understanding of the invention can be obtained by reference to the following detailed description of the preferred embodiments thereof in connection with the attached drawings.